#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_set>
using namespace std;
//class Solution {
//public:
//    vector<int> subSort(vector<int>& array) {
//        if (0 == array.size())
//            return { -1,-1 };
//        vector<int> v(array.begin(), array.end());
//        std::sort(v.begin(), v.end());
//        int m = -1, n = -1;
//        for (int i = 0;i < array.size();++i)
//        {
//            if (v[i] != array[i])
//            {
//                if (-1 == m)
//                    m = i;
//                else
//                    n = i;
//            }
//        }
//        return { m,n };
//    }
//}

void frontBack(vector<int>& v)
{
    //只要back遇到奇数时停下，prev总是想指向偶数
    int prev = 0, back = 0;
    while (back < v.size())
    {
        if ((v[back] & 1) == 1)
        {
            int tmp = v[back];
            int k = back;
            if (k > prev)
            {
                v[k] = v[k - 1];
                --k;
            }
            v[prev++] = tmp;
        }
        ++back;
    }
}

class Object
{
public:
    bool operator()(const string& str1,const string& str2)const
    {
        return str1.length() < str2.length();
    }
};

//字典树
struct Node
{
    int val;
    Node* children[26];
    Node()
    {
        val = 0;
        for (int i = 0;i < 26;++i)
            children[i] = nullptr;
    }
};

class Trie
{
public:
    Trie()
    {
        root = new Node();
    }
    ~Trie()
    {
        release(root);
    }
    void release(Node* node)
    {
        for (int i = 0;i < 26;++i)
        {
            if (node->children[i])
            {
                release(node->children[i]);
            }
        }
        delete node;
    }
    void insert(const string& str)
    {
        Node* node = root;//从根节点开始插，树中已有的单词就不用再插了
        for (int i = 0;i < str.length();++i)
        {
            if (nullptr == node->children[str[i] - 'a'])
            {
                node->children[str[i]-'a'] = new Node();
            }
            node = node->children[str[i]-'a'];
        }
        node->val = -1;
    }
    unordered_set<string>& grepPrefixStr(const string& prefix)
    {
        //对上一次的myset中的字符串清空
        if (!strset.empty())
            strset.clear();
        Node* position = root;//从根节点开始找

        for (int i = 0;i < prefix.length();++i)
        {
            if (nullptr == position->children[prefix[i] - 'a'])
                return strset;
            else
                position = position->children[prefix[i] - 'a'];
        }

        //从postion位置处开始递归，获取字符串
        string s = prefix;
        recursion(position,s);
        return strset;
    }
    void recursion(Node* position,string& s)
    {
        //要求是：如果插入到字典树中的字符串是要搜索的前缀，那么也要返回该字符串
        if (position->val == -1)
            strset.emplace(s);
        bool flag = false;
        //下面代码用到了回溯算法思想
        for (int i = 0;i < 26;++i)
        {
            if (position->children[i] != nullptr)
            {
                flag = true;
                s.push_back('a' + i);
                recursion(position->children[i], s);
            }
        }
        if(false == flag)
        strset.emplace(s);
        s.pop_back();
    }
    
private:
    Node* root = nullptr;
    unordered_set<string> strset;
};

int main()
{
    /*vector<string> v = { "strstr","strhh","strkkjkl","str"};
    Trie t;
    for (const auto& str : v)
        t.insert(str);
    unordered_set<string> myset = t.grepPrefixStr("str");
    for (const auto& str : myset)
        cout << str << endl;*/

    unordered_set<int> myset({9999,8998,4342,2312,1213,10,6,5,4,3,2,1});
    myset.insert(myset.begin(),9090);
    


    //vector迭代器失效：
    /*vector<int> v({ 1,2,3 });
    vector<int>::iterator it1 = v.begin();
    it1[0] = 6;
    cout << v[0];
    一、insert会出现迭代器失效
    v.insert(it1, { 1,2,4 }); //插入数据是向指定位置的前面插入
    v.insert(v.end(), 4);
    v.push_back(8);
    二、erase不会出现迭代器失效
    v.erase(v.end() - 1);
    cout << *(it1+1);*/

    ////string
    //string s = "abcde";
    //string::iterator it = s.begin();
    ////insert不会出现迭代器失效
    //s.insert(it + 1, 'a');
    ////cout << *it;
    ////erase不会出现迭代器失效
    //s.erase(2);
    //cout << *it;

    //int a = -3;
    //cout << ~(-8); //& ^ | 都是在对补码进行操作
    //unordered_set<string> myset;
    //vector<string> v{ "abs", "a", "cd", "csx" };
    //std::sort(v.begin(), v.end(),Object());
    //for (const auto& str : v)
    //    cout << str << endl;

    //ifstream打开文件
    //string s;
    //vector<string> vv;
    //std::ifstream file("C:/Users/86180/source/repos/TestFile/TestFile/content.txt");//文件一定要写清楚后缀
    //if (!file.is_open())
    //    return 1;
    //while (std::getline(file, s))
    //{
    //    vv.push_back(s);
    //}
    //cout << vv[1];
    //file.close();
    return 0;
}